Fast Fourier Transform

algorithm (FFT) An algorithm for computing the Fouriertransform of a set of discrete data values. Given a finite

set of data points, for example a periodic sampling taken from

a real-world signal, the FFT expresses the data in terms of

its component frequencies. It also solves the essentially

identical inverse problem of reconstructing a signal from the

frequency data.

The FFT is a mainstay of numerical analysis. Gilbert Strang

described it as "the most important algorithm of our

generation". The FFT also provides the asymptotically fastest

known algorithm for multiplying two polynomials.

Versions of the algorithm (in C and Fortran) can be found

on-line from the GAMS server here.

["Numerical Methods and Analysis", Buchanan and Turner].

(1994-11-09)